#dijkstra最短路径算法

from heapq import heappop, heappush

def dijkstra(graph, weight, source=0, target=None):
    """dijkstra最短路径算法
        :param graph：list(list)或list(dict)格式的定向图
        :param weight：矩阵或邻接字典
        :param int source：节点
        :param target：目标点，找到则停止遍历
        :返回：距离表，前置表
        :复杂度: `O(|V| + |E|log|V|)`
    """
    n = len(graph) #节点个数
    assert all(weight[u][v] >= 0 for u in range(n) for v in graph[u]) #必须为非负权重
    prec = [None] * n #节点的前置节点
    black = [False] * n #已经遍历过的节点
    dist = [float('inf')] * n #回到起始点的距离
    dist[source] = 0 #起始点到起始点距离为0
    heap = [(0, source)] #最小堆队列
    while heap: 
        dist_node, node = heappop(heap)   #选取距离起点最近的节点
        if not black[node]: #已经标黑，则跳过
            black[node] = True  #开始(被)遍历则标黑
            if node == target: #找到目标点，则停止遍历
                break
            for neighbor in graph[node]:
                dist_neighbor = dist_node + weight[node][neighbor]
                if dist_neighbor < dist[neighbor]:
                    dist[neighbor] = dist_neighbor #更新距离
                    prec[neighbor] = node    #更新前者节点
                    heappush(heap, (dist_neighbor, neighbor)) #加入队列
    return dist, prec

